BZOJ 1109 堆积木Klo

Description

Mary在她的生日礼物中有一些积木。那些积木都是相同大小的立方体。每个积木上面都有一个数。Mary用他的所有积木垒了一个高塔。妈妈告诉Mary游戏的目的是建一个塔,使得最多的积木在正确的位置。一个上面写有数i的积木的正确位置是这个塔从下往上数第i个位置。Mary决定从现有的高塔中移走一些,使得有最多的积木在正确的位置。请你告诉Mary她应该移走哪些积木。

Input

输入文件的第一行为一个数n,表示高塔的初始高度。第二行包含n个数a1,a2,…,an,表示从下到上每个积木上面的数。(1<=n<=100000,1<=ai<=1000000)。

Output

注意:请输出最多有多少点可以处在正确位置

Sample Input

5
1 1 2 5 4

Sample Output

3

Hint

Solution

本来是想来做POI水题,结果看了好多题解……
这道题自己yy了一个二维的DP,不能优化,然后狗带了
可以用正解优化的是f[i]表示i在正确位置时1~i中最多有多少个在正确位置
显然有$f[i]=max(f[j])+1 ( j0 \&\& a[i]-a[j]<=i-j )$
观察发现满足后两个等式时j<i
然后直接拿后面两个排序+LIS
听说叫三维偏序?现在想想感觉cdq也可以搞

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>

#define maxn 100000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct data{
int x,y;
}a[maxn];

int h[maxn],tail;
int n,ans;

bool comp(data a,data b)
{

return a.x==b.x ? a.y<b.y : a.x<b.x ;
}

void div2(int x)
{

int l=1,r=tail;
while( l<r ){
int mid=(l+r)/2;
if( h[mid]>=x ) l=mid+1;
else r=mid;
}
h[l]=x;
}

void DP()
{

sort(a+1,a+n+1,comp);
for(int i=1;i<=n;i++){
if( h[tail]>=a[i].y ) h[++tail]=a[i].y;
else if( a[i].y<=0 ) div2(a[i].y);
ans=max(ans,tail);
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("1109.in","r",stdin);
freopen("1109.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i].x),a[i].y=a[i].x-i;
DP();
printf("%d",ans);
return 0;
}